import java.util.ArrayList;
import java.util.List;

/**
 * @Author: linzp
 * @Date: 2021/12/13/17:46
 * 分割类型题
 * 对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割
 * 条件的位置
 */
public class solution74 {
    public static void main(String[] args) {
        numDecodings("12");
    }
    public static int numDecodings(String s) {
        int len = s.length();
        s =  " " + s;//错误示范""+s
        char[] cs = s.toCharArray();//以上两步为了转字符数组 并且初始化了char[0] = ' ';
        int[] dp = new int[len + 1];
        dp[0] = 1;
        for (int i = 1; i <= len; i++) {
            int a = cs[i] - '0',  b = (cs[i - 1] - '0') * 10 + cs[i] - '0';
            if (a >= 1 && a <= 9) {
                dp[i] += dp[i - 1];
            }
            if (i>1&&b <= 26 && b >= 10) {
                dp[i] += dp[i - 2];
            }


        }
        return dp[len];
    }
}

/**
 * 279. 完全平方数
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 *
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 *dp[i] 表示硬币为i个时 的最少组成数是多少
 */
class Solution279 {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[0]=0;
        for (int i = 1; i <= n; i++) {
            dp[i]=i;//最坏的情况下，都是1组成的
            for (int j = 1; j*j<=i; j++) {//分别表示1-n 时的最小组成数
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}


/*------------------------------------------------------91-------------------------------------------------------------------*/

/**
 * 91. 解码方法
 * 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
 *
 * "AAJF" ，将消息分组为 (1 1 10 6)
 * "KJF" ，将消息分组为 (11 10 6)
 * 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
 *
 * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
 *
 * 题目数据保证答案肯定是一个 32 位 的整数。
 *
 *
 * 只能由位置 i 的单独作为一个 item，设为 a，转移的前提是 a 的数值范围为 [1,9][1,9]，转移逻辑为 f[i] = f[i - 1]f[i]=f[i−1]。
 * 只能由位置 i 的与前一位置（i-1）共同作为一个 item，设为 b，转移的前提是 b 的数值范围为 [10,26][10,26]，转移逻辑为 f[i] = f[i - 2]f[i]=f[i−2]。
 * 位置 i 既能作为独立 item 也能与上一位置形成 item，转移逻辑为 f[i] = f[i - 1] + f[i - 2]f[i]=f[i−1]+f[i−2]。
 * 因此，我们有如下转移方程：
 *
 * 可以走两步楼梯或者一步楼梯。。进阶版
 * f[i]=f[i−1],1⩽a≤9
 * f[i]=f[i−2],10⩽b⩽26
 * f[i]=f[i−1]+f[i−2],1⩽a≤9,10⩽b⩽26
 * ​
 *
 *

 *
 */
class Solution91 {
    public int numDecodings(String s) {
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        for (int i = 1; i <= len; i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i >= 2 && (s.charAt(i - 2) == '1' || (s.charAt(i - 1) <= '6' && s.charAt(i - 2) == '2'))) {//10-19 20-26
                dp[i] += dp[i - 2];
            }
        }
        return dp[len];
    }
}

class Solution91_1 {
    public static void main(String[] args) {
        numDecodings("12");
    }
    public static int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }
}

class Solution91_2 {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

/*--------------------------------------------------139-----------------------------------------------------------------------*/
/**
 * 139. 单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
 *
 * 说明：拆分时可以重复使用字典中的单词。
 *
 *
 *
 * 示例 1：
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 */

class Solution139 {
    public static void main(String[] args) {
        List<String> list= new ArrayList<>();
        list.add("le");
        list.add("co");
        System.out.println("leco".substring(2, 2));
        System.out.println(wordBreak("leco",list));
        wordBreak("leco",list);
    }
    public static boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];//init full false
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (String str : wordDict) {
                int strLen = str.length();
                if (i - strLen >= 0 && s.substring(i - strLen, i).equals(str)) {
                    dp[i] = dp[i - strLen] || dp[i];//与 strLen有关
                }
            }
        }
        return dp[len];
    }
}
